package com.demo.datastructure.binarySearch;

/**
 * @description: LETCODE 33  搜索旋转排序数组
 * @author: ljr
 * @time: 2021/5/14 13:38
 */
public class BinarySearch10 {

    public static int bsearch(int[] nums, int target) {
        int n = nums.length;
        if(n == 1){
           return nums[0] == target? 0:-1;
        }

        int low = 0;
        int high = n-1;

        int num = nums[0];
        while (low <= high){
            int mid = low +(high-low >> 1);
            if(nums[mid] < num){
                high = mid -1;
            }else{
                if(mid == n-1 || nums[mid+1] < num){
                    low = mid;
                    break;
                }
                low = mid+1;
            }
        }

        int index = low;
        if(index == n-1 || target >= num){
            low = 0;
            high = index;
        }else{
            low = index+1;
            high = n-1;
        }

        while (low <= high) {
            int mid = low + (high - low >> 1);
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                high = mid-1;
            }else{
                low = mid+1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
       //int[] nums = new int[]{3,1};
       int[] nums = new int[]{4,5,6,7,0,1,2};
       int index = BinarySearch10.bsearch(nums,5);
       System.out.println(index);
    }
}
